1. Field of the Invention
The present invention generally relates to database technology, and more specifically, to a way of accelerating content-based retrieval of visual objects by use of indexing techniques.
2. Description of the Related Technology
Recently, a need has developed to search very large databases of visual objects, such as images, which may contain upwards of one million or more images. Since content-based retrieval allows for the defining of more than one primitive (each primitive being associated with a visual characteristic such as color, texture, shape, and so forth) per image and each primitive requires significant computation, comparisons in a large search space become computationally intensive. Thus, the technical challenge of scalability in content-based retrieval is addressed by the present invention.
Collections of electronic images can effectively be searched using a content-based retrieval search engine. For instance, an image search engine can be licensed from Virage, Inc. of San Mateo, Calif. The Virage search engine is described in U.S. patent application Ser. No. 08/829,791, filed Mar. 28, 1997.
A search engine typically comprises two phases: analysis and comparison. The analysis phase characterizes images stored in the system or referenced by the system by predefined or user defined primitives. Each primitive extracts visual feature data which is combined into a feature vector. In the comparison phase, a target or query feature vector is compared to the feature vectors which have previously been computed. These feature vectors are typically stored in a database. The target feature vector represents, for example, an image for which the user desires to find similar images.
Referring to FIG. 1, an image(i) 102, i.e., the i-th image stored in the database, is fed into an analysis phase module 104 of a visual information retrieval (VIR) engine 100 for analysis. In the analysis phase 104, a feature vector (i) 106 for the image is extracted and stored into a database 108. This process is repeated until all stored images have been analyzed and had associated feature vectors created and stored. In a comparison phase, a feature vector (target) 110 is fed into a comparison phase module 112 VIR engine and the VIR engine sequentially computes distances between the target feature vector 110 and each feature vector(i) 106 stored in the database 108. The comparison is made between individual feature vectors using a distance metric associated with a primitive. The distance is then selectively weighted using user-defined weights 114 and weighted distances are combined to provide an output score 116 for each comparison. The output score 116 is a scalar which can be used to select the best result or rank order the results for further searching. For instance, in a stock photography scenario, a publisher may desire to see photographs of sunsets which satisfy a certain criteria established by selecting weights 114. A set of thumbnail sketches may be presented on a visual display showing the results to the publisher and allowing for refinement by repetitive searching.
Typically this process must compute a distance between the feature vector 110 of the target image and every other feature vector 106 referenced by the system. This may require an enormous amount of time and computing resources, but will guarantee that the most similar images are identified. The amount of time required for this approach includes the time required to compute the visual distance, as well as the time required to retrieve every feature vector 106 into memory. If the feature vectors 106 are stored in a commercial database system, this retrieval time will be considerable.